package DynamicProgramming;

import java.util.Arrays;
import java.util.Scanner;

class AtkinSieve_1586
{	private int limit;
	private boolean isPrime[];
	
	public AtkinSieve_1586(int l)
	{	limit=(l>=5?l:5);
		MakeSieve();
	}
	private void MakeSieve()
	{	isPrime=new boolean[limit+1];
		Arrays.fill(isPrime, false);
		isPrime[2]=true;isPrime[3]=true;
		
		int cap=(int)Math.sqrt(limit);
		for (int x=1;x<=cap;x++)
			for (int y=1;y<=cap;y++)
			{	int n;
				n = 4*x*x+y*y;
				if (n<=limit && (n%12==1 || n%12==5))
					isPrime[n]=!isPrime[n];
				n = 3*x*x+y*y;
				if (n<=limit && n%12==7)
					isPrime[n]=!isPrime[n];
				n = 3*x*x-y*y;
				if (x>y && n<=limit && n%12==11)
					isPrime[n]=!isPrime[n];
			}
		for (int i=5;i<=cap;i++)
			if (isPrime[i])
				for (int j=1,t=i*i; t*j<=limit; j++)
					isPrime[t*j]=false;
	}
	public int getLimit()
	{	return limit;
	}
	public void setLimit(int limit)
	{	this.limit = limit;
	}
	public boolean isPrime(int k)
	{	return isPrime[k];
	}
}
class Solver_1586
{	public void main()
	{	Scanner in=new Scanner(System.in);
		AtkinSieve_1586 sieve=new AtkinSieve_1586(1000);
		int n=in.nextInt();
		long curEndBy[]=new long[100], nxtEndBy[]=new long[100];
		long mod=(long)(Math.pow(10,9)+9), rs=0;
		
		int NextBy[][]=new int[100][];
		for (int i=0;i<100;i++)
		{	int count=0;
			for (int j=0;j<10;j++)
				if (sieve.isPrime(i*10+j))
					count++;
			NextBy[i]=new int[count];
			count=0;
			for (int j=0;j<10;j++)
				if (sieve.isPrime(i*10+j))
					NextBy[i][count++]=(i*10+j)%100;
		}
		Arrays.fill(curEndBy, 0);
		for (int i=100;i<1000;i++)
			if (sieve.isPrime(i))
				curEndBy[i%100]++;
		
		for (int i=4;i<=n;i++)
		{	for (int j=0;j<100;j++) nxtEndBy[j]=0;
			for (int j=0;j<100;j++)
			{	long ct=curEndBy[j];
				if (j<10) continue;
				for (int k=0;k<NextBy[j].length;k++)
				{	nxtEndBy[NextBy[j][k]]+=ct;
				}
			}
			for (int j=0;j<100;j++) nxtEndBy[j]%=mod;
			long[] tmp=curEndBy;curEndBy=nxtEndBy;nxtEndBy=tmp;
		}
		
		for (int i=0;i<100;i++)
			rs+=curEndBy[i];
		rs%=mod;
		System.out.println(rs);
		in.close();
	}
}
public class P1586
{	public static void main(String[] args)
	{	Solver_1586 sv=new Solver_1586();
		sv.main();
	}
}
